/**
 * 449. 序列化和反序列化二叉搜索树
 * https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
 */
public class Solutions_449 {
    public static void main(String[] args) {
//        String str = "[2 1 3]";
        String str = "[2 1]";
//        String str = "[]";
        TreeNode root = MyTreeNodeUtils.deserialize(str);
        Codec_449 obj = new Codec_449();

        String res1 = obj.serialize(root);
        System.out.println(res1);
        TreeNode res2 = obj.deserialize(res1);
        System.out.println(MyTreeNodeUtils.serialize(res2));
    }
}

/**
 * 利用二叉搜索树的特性：不使用层次遍历，而是先序遍历，那么编码的字符串会更加紧凑（不需要占位符）
 *      2
 *    /  \
 *   1   3
 * 根据先序遍历原则，序列化为：[2,1,3]
 * 反序列化，根节点是 2，索引为 0，那么在数组中找到第一个大于根节点 2 的元素 (3) 所在的索引 2
 * 即 [0 + 1, 2 - 1] 区间的元素就是根节点的左子树，[2, len - 1] 区间的元素就是根节点的右子树
 * 再通过递归完成子树的构建
 */
class Codec_449 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        dfs(sb, root);
        sb.deleteCharAt(sb.length() - 1);
        sb.append(']');
        return sb.toString();
    }

    public void dfs(StringBuilder sb, TreeNode root) {
        if (root == null) {
            return;
        }
        // 先序遍历：根左右方式，利用二叉搜索树性质
        sb.append(root.val);
        sb.append(',');
        dfs(sb, root.left);
        dfs(sb, root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || "[]".equals(data)) {
            return null;
        }
        // 去除括号 "[]"
        data = data.substring(1, data.length() - 1);
        String[] nodes = data.split(",");
        int[] nodeVal = new int[nodes.length];
        for (int i = 0; i < nodes.length; i++) {
            nodeVal[i] = Integer.valueOf(nodes[i]);
        }
        return builder(0, nodes.length - 1, nodeVal);
    }

    public TreeNode builder(int left, int right, int[] nodeVal) {
        if (left >= right) {
            // 结束条件
            return left > right ? null : new TreeNode(nodeVal[left]);
        }
        // 第一个节点，即是根结点
        int curVal = nodeVal[left];
        TreeNode root = new TreeNode(curVal);
        // 在 [1, nodes.length - 1] 区间中找到第一个比 rootVal 大的数，并将所在索引赋给 idx
        // 若是在 nodeVal 中没有找到比 curVal 大的元素，说明 [1, nodes.length - 1] 中的元素，都是 root 的左子树元素，
        // 而 root 的右子树为 null，所以给定 idx 的默认值为 right + 1，若是有右子树，则 idx 会改变
        int idx = right + 1;
        for (int i = left + 1; i <= right; i++) {
            if (nodeVal[i] > curVal) {
                // 找到右子节点
                idx = i;
                break;
            }
        }
        // 构建左子树，元素区间：[left + 1, idx - 1]
        root.left = builder(left + 1, idx - 1, nodeVal);
        // 构建右子树，元素区间：[idx, right]
        root.right = builder(idx, right, nodeVal);
        return root;
    }
}
